在山脉数组中查找元素Leetcode162,Leetcode 852,Leetcode1095和Leetcode941

典型的题目有：Leetcode 162. 寻找峰值 和 Leetcode 852. 山脉数组的峰顶索引，都是要找出数组中峰值元素的索引。峰值元素的取值比它两边的元素要大，就像山峰的峰顶一样，因此这种数组也被称为山脉数组。

题目要求使用代码的时间复杂度是 O(log n)，我们首先想到用二分查找法。可是，数组的元素有起伏变化，还能用二分查找吗？仔细观察会发现，其实峰值的两侧都是有规律地变化：单调递增或递减。Leetcode 852 的数组中只有一个峰值元素。而 Leetcode 162 的数组可能有多个峰值元素，可以把元素的取值变化想象成相邻的多个小山坡，或者波浪型，两个峰值之间的元素也分段符合单调递增或递减规律，因此可以采用相同的思路。

用二分查找解决这类问题的关键点：不是寻找一个确定值 target，而是寻找一个有峰值特征的元素，也就是这个元素比两边元素的值要大。只要修改二分查找中对 middle 元素的判断条件如下：

细节：数组首尾元素。这个方法应用于数组首尾元素，例如 middle = length(nums) - 1 时，nums[middle +1] 超出索引范围，会报错。因此，搜索区间初始为 [ 1, length -2 ]。而判断是否为峰值元素时，区间要有至少 3 个元素： arr[mid-1] < arr[mid] < arr[mid+1]，因此，应用二分查找时数组长度不小于 3。

这里以 Leetcode 852 为例，其代码为：

Leetcode 1095. 山脉数组中查找目标值 这道题基于 Leetcode 852 ，但更难一些，还要在数组中寻找一个目标值。因为这个数组是山脉数组，如果目标值出现了两次，题目要求返回较小的索引值。

解题的关键在于要先找到峰值元素，以该元素为界把整个数组划分成递增数组和递减数组。 接下来就容易了，只要先在峰值元素的左区间、再在右区间应用二分查找寻找目标值。先查找左区间、再查找右区间是为了返回符合条件的较小索引。总体要做 3 次二分查找。

当我理解了这道题的解题思路之后，就用 Leetcode 852 的方法寻找峰值。但是代码运行报错：调用 MountainArray.get(k) 函数超过了 100 次限制。我看了这个解答，发现如果用 while low < high，判断条件会简化，因此调用 MountainArray.get(k) 函数次数也会减少。相应的代码及注释如下：

注：我用此方法再做一遍 Leetcode 852 ，发现它比前面使用的 while low bool: length = len(arr) # 判断条件(1)：山脉数组的长度不小于3 if length 0 and arr[right - 1] > arr[right]: right -= 1 # 此时左右指针都指向了某个峰值元素，也就是爬到了某个山顶 # 判断条件(2)：山脉数组只有一个山顶，左右指针指向的是同一个山顶吗？ if left == right: return True else: return False 参考 Leetcode 162 思路：Intuition behind conditions Leetcode 1095 思路：[Java/C++/Python] Triple Binary Search - Find in Mountain Array - LeetCodeLeetcode 941 思路：[C++/Java/Python] Climb Mountain - Valid Mountain Array - LeetCode